import collections
class Solution(object):
    def minimumFinishTime(self, tires, changeTime, numLaps):
        d = collections.defaultdict(lambda: float('inf'))
        for f, r in tires:
            d[1] = min(d[1], f)
            index = 1
            num = f
            total = f
            while num * r <= f + changeTime:
                num *= r
                total += num
                index += 1
                d[index] = min(d[index], total)
        max_key = max(d.keys())
        ans = [float('inf')] * numLaps
        for i in range(numLaps):
            for j in range(1, max_key + 1):
                if i - j < 0:
                    ans[i] = min(ans[i], d[j])
                    break
                else:
                    ans[i] = min(ans[i], d[j] + ans[i - j] + changeTime)
        return ans[-1]


data = Solution()
tires = [[2,3],[3,4]]
changeTime = 5
numLaps = 4
print(data.minimumFinishTime(tires, changeTime, numLaps))